package dp;

/**
 * @author tmh
 * @date 2024/9/16 22:14
 * @description
 */
public class T1049最后一块石头的重量II {
    // 这个题和分割等和子集的题差不多，只是问题描述不一样罢了，抽象出来的问题都一样
    // 把这些石头分成两堆,往容量为sum/2的背包里面装石头，能够装的最大价值的石头和sum减去这一部分作比较
    //得到的就是最后相撞剩下的石头，和子集题目的区别就是返回值的不同，顺带增加了点理解
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        int len = stones.length;
        int[][] dp = new int[len][target + 1];
        for (int i = stones[0]; i <= target; i++) {
            dp[0][i] = stones[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= target; j++) {
                //不取这个物品==》物品的重量大于背包的容量
                if (stones[i] > j) {
                    dp[i - 1][j] = dp[i][j];
                }
                //取这个物品
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                }
            }
        }
        return Math.abs(dp[len - 1][target] - (sum - dp[len - 1][target]));
    }
}
